Theo gia phả họ Đỗ tại làng Đại Mão, Đỗ Trọng Vĩ sinh ngày 12 tháng 10 (âl) năm Kỷ Sửu 1829, quê làng Đại Mão, huyện Siêu Loại, phủ Thuận An, trấn Kinh Bắc (nay thuộc xã Hoài Thượng, huyện Thuận Thành, tỉnh Bắc Ninh). Cũng theo gia phả, ông là hậu duệ của Trạng nguyên Nguyễn Quang Bật thời nhà Lê. Cha ông là cụ Đỗ Dư (hay Đỗ Trọng Dư), tự Hòa Trai, hiệu Hy Liễu, nổi tiếng học rộng tài cao, đỗ Cử nhân khoa Kỷ Mão 1819, từng làm đến chức Tri phủ Quốc Oai. Năm 1826, sau khi bị triều đình xét tội cách chức, cụ về quê làm nghề dạy học, đào tạo được nhiều thế hệ học trò thành danh. Cụ là tác giả của các tác phẩm Quan Âm truyện, Âm Chất truyện, nổi tiếng đương thời.

Khi Đỗ Trọng Vĩ mới lên 3 thì thân mẫu qua đời, ông được bên ngoại đón về Thụy Chương (nay thuộc quận Tây Hồ, Hà Nội) nuôi nấng. Đến năm lên 6 tuổi, ông được cha đón về trực tiếp nuôi dạy. Xuất thân từ một gia đình có truyền thống khoa bảng, từ nhỏ lài có tiếng thông minh đĩnh ngộ, học chóng hiểu thông và biết làm thơ sớm, ông sớm nổi tiếng văn tài Nho học. Năm 21 tuổi, ông đỗ Tú tài khoa Canh Tuất 1850.